Several protocols can be used in an Ad Hoc On-Demand Distance Vector (AODV) routing protocol to accommodate interruptions in a communication path within a Wireless Sensor Network (WSN). Some routing protocols implement solutions to a flooding problem in on-demand routing protocols by enhancing route recovery mechanisms.
In AODV with Backup Routing (AODV-BR), nodes overhear route reply messages of their neighbors to create their own alternate routes to a destination. When a node detects a broken route, it broadcasts a packet concerning the broken route to its neighbors in case one of them has a valid route to the destination. At the same time, the node sends a route error (RERR) message to the source to initiate a route rediscovery. One reason for reconstructing a new route instead of continuously using the alternate path is to build a fresh and optimal route that reflects the current status of the network. AODV-BR concentrates on increasing route reliability by decreasing packet drop rates, but it suffers from problems with stale routes and duplicate packet transmission.
In Neighborhood-aware Source Routing (NSR) protocol, each node has a partial topology that covers the links in requested paths to destinations, in addition to the 2-hop neighborhood. See Spohn, M. and Garcia-Luna-Aceves, J. J. 2001. Neighborhood aware source routing, in Proceedings of 2nd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), incorporated herein by reference in its entirety. Link state information is maintained by broadcasting periodic HELLO messages. In case of a route failure, an intermediate node tries to repair the route if either the link to the next hop has failed or the link headed by the next hop on the path to be traversed has failed. The RERR message is propagated to the source node if an intermediate node uses a completely new route to the destination or it has no alternate route to the destination. HELLO messages in NSR protocol incur excessive overhead to maintain the partial topology of the network. In addition, stale route problems may affect the performance of NSR protocol.
Dynamic Source Routing (DSR) protocol can be suitable for networks with relatively small diameters and in which the mobile nodes move at a moderate speed with respect to packet transmission latency. It potentially caches multiple routes to a destination and provides a route salvaging option that enables intermediate nodes to recover from route failure locally by searching for an alternate route. Even with successful salvaging, intermediate nodes immediately send a RERR message back to the source to notify it about a route failure. The source node can check its cache for another valid route. If such a route is found, route reconstruction does not need to be invoked. If there are no additional routes to the destination in the source node's cache, route discovery is reinitiated. However, DSR protocol is not scalable to large networks. In addition, the failure may occur far away from the sender and close to the destination and with no alternate routes available. When the packet has succeeded in traversing most of the path, this length of successful path traversal is not exploited. This increases the overall packet delivery time and the network resources used by the routing protocol. Furthermore, DSR protocol incurs more packet drop and delay due to its dependency on stale routes.
Bypass routing is a local recovery protocol that attempts to reduce the frequency of route request floods triggered by broken routes, by localizing the reaction to route failures using on-demand local recovery and a cache-invalidation mechanism. The mechanism uses link-state information to find a patch between one of the neighbors and a node along the route to the destination. This mechanism is suitable for source routing protocols where complete route information is stored for each route entry. When a link between two nodes is broken, the node that detects the failure tries to patch the route by looking for a bypass route which connects the node with any of the downstream nodes of the broken route. If such a route is unavailable, the node triggers a local query to its neighbors to see if one of them has a valid route to any of the downstream nodes of the broken link. If neither the intermediate node nor its neighbors has an alternate route, the bypass routing is equivalent to DSR protocol, but with further overhead and delay increases. Bypass routing does not propose any solution for the stale route problem that exists in DSR protocol. Furthermore, bypass routing is only applicable to on-demand routing protocols where complete route information is included in the transmitted data packet.
Multipath routing provides fault tolerance by caching multiple routes to a destination in a single route-discovery cycle. When a link breaks, an alternative route can be used to route the packets. Although multipath processes utilize network resources, they incur more packet drop and delay due to their dependency on stale routes. On the other hand, local repair processes introduce a special route maintenance method to repair broken routes. In AODV routing protocol, the upstream node decides either to repair the route via a limited broadcast or to send a RERR message to the source node based on its distance from the destination node when a link in the route breaks. To repair the broken route, if the node is close to the destination, it sends a route request (RREQ) message with a limited time-to-live (TTL) value. Otherwise, the RERR message is propagated to the source node to start a new route discovery process. After starting the repair process, the node waits for a discovery period. If the repair attempt fails, a RERR message is sent back to the source node. Otherwise, the node updates its routing entry. Local repair processes use a large bandwidth. Even with a limited broadcast, flooding can deliver the RREQ messages to a large number of nodes, leading to high routing overheads. In addition, a route maintained by a local repair process may no longer be the optimal route at a future time. In AODV routing protocol, local repair schemes also lack an efficient way to handle link breaks that are close to the source node. Those route breaks are handled by propagating a RERR message to the source node to start a new route discovery cycle, which leads to further packet drop and bandwidth consumption. Results indicate more than 50% of route failures are close to the source side than to the destination side.
The “background” description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description which may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.